|
In graph theory, a branch of mathematics and computer science, the Chinese postman problem (CPP), postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of a (connected) undirected graph. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal solution. Otherwise, the optimization problem is to find the fewest number of edges to add to the graph so that the resulting multigraph does have an Eulerian circuit. Alan Goldman of the U.S. National Bureau of Standards first coined the name 'Chinese Postman Problem' for this problem, as it was originally studied by the Chinese mathematician Kwan Mei-Ko in 1960, whose Chinese paper was translated into English in 1962.〔 - NIST〕 ==Eulerian paths and circuits== In order for a graph to have an Eulerian circuit, it will certainly have to be connected. Suppose we have a connected graph ''G'' = (''V'', ''E''), The following statements are equivalent: # All vertices in G have even degree. # G consists of the edges from a disjoint union of some cycles, and the vertices from these cycles. # G has an Eulerian circuit. * 1 → 2 can be shown by induction on the number of cycles. * 2 → 3 can also be shown by induction on the number of cycles, and * 3 → 1 is immediate. An Eulerian path (a walk which is not closed but uses all edges of G just once) exists if and only if G is connected and exactly two vertices have odd valence (degree). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Route inspection problem」の詳細全文を読む スポンサード リンク
|